package com.leetcode.题库;

import java.util.Arrays;

/**
 * @author 覃国强
 * @date 2022-02-26 19:35
 */
public class 题库_0016_最接近的三数之和 {

  static
  class Solution {
    public int threeSumClosest(int[] nums, int target) {
      Arrays.sort(nums);
      int closestSum = nums[0] + nums[1] + nums[2];
      for (int i = 0; i < nums.length; ++i) {
        if (i > 0 && nums[i] == nums[i - 1]) {
          continue;
        }
        int left = i + 1;
        int right = nums.length - 1;
        while (left < right) {
          int curSum = nums[i] + nums[left] + nums[right];
          if (Math.abs(target - curSum) < Math.abs(target - closestSum)) {
            closestSum = curSum;
          }

          if (curSum < target) {
            ++left;
            while (left < right && nums[left] == nums[left - 1]) {
              ++left;
            }
          } else if (curSum > target) {
            --right;
            while (left < right && nums[right] == nums[right + 1]) {
              --right;
            }
          } else {
            return closestSum;
          }
        }
      }
      return closestSum;
    }
  }

}
